package de.unibi.comet.ac;

import java.util.Iterator;
import java.util.LinkedList;
import java.util.Stack;
import java.util.NoSuchElementException;
import java.lang.UnsupportedOperationException;
import de.unibi.comet.util.EmptyIterator;

public class EnhancedSuffixArray implements SuffixStructure {

	private String string;
	private int [] suffixArray;
	private NodeTableElement [] nodeTable;
	
	private class NodeTableElement {
		int prevChild;
		int lcp;
		int start;
		int end;
		int parent;
		NodeTableElement(int lcp, int start, int end) {
			this.prevChild=-1;
			this.lcp=lcp;
			this.start=start;
			this.end=end;
			this.parent=-1;
		}
	}
	
	private class SingletonNode extends AbstractSuffixStructureNode {
		int sa_idx;
		int parent_idx;
		SingletonNode(int sa_idx, int parent_idx) {
			this.sa_idx=sa_idx;
			this.parent_idx=parent_idx;
		}
		public Iterator<SuffixStructureNode> childrenIterator() { return new EmptyIterator<SuffixStructureNode>(); }
		public int getOneIndex() { return suffixArray[sa_idx]; }
		public String getText() {
			StringBuffer sb = new StringBuffer();
			for (int i=suffixArray[sa_idx]; i<string.length(); i++) {
				char c = string.charAt(i);
				if (c=='$') break;
				sb.append(c);
			}
			return sb.toString();
		}
		public boolean isSuffix() { return true; }
		public boolean isRoot() { return false; }
		public SuffixStructureNode getChildByChar(char c) { return null; }
		public SuffixStructureNode getParent() { return new Node(parent_idx); }
		public String getEdgeText() {
			StringBuffer sb = new StringBuffer();
			int i = suffixArray[sa_idx] + nodeTable[parent_idx].lcp;
			for (; i<string.length(); i++) {
				char c = string.charAt(i);
				if (c=='$') break;
				sb.append(c);
			}
			return sb.toString();
		}
		public int getNumber() {
			return nodeTable.length + sa_idx;
		}
		@Override
		public boolean equals(Object obj) {
			if (!(obj instanceof SingletonNode)) return false;
			return (sa_idx==((SingletonNode)obj).sa_idx) && (parent_idx==((SingletonNode)obj).parent_idx);
		}
	}

	private class ChildrenIterator implements Iterator<SuffixStructureNode> {
		private int nextNodeIdx;
		private int parentIdx;
		private int parentIntervalStart;
		private int parentLcp;
		private int singletonPointer;
		
		ChildrenIterator(int parentIdx) {
			this.parentIdx=parentIdx;
			this.parentIntervalStart=nodeTable[parentIdx].start;
			this.parentLcp=nodeTable[parentIdx].lcp;
			this.singletonPointer=nodeTable[parentIdx].end;
			if (hasChild(parentIdx)) this.nextNodeIdx=parentIdx+1;
			else this.nextNodeIdx=-1;
		}

		private int getNextNodeIndex(int idx) {
			return nodeTable[idx].prevChild;
		}
		
		private boolean singletonValid() {
			// is singletonPointer still in a valid range?
			if (singletonPointer<parentIntervalStart) return false;
			// check if singleton would have same text as parent interval,
			// if so --> return false
			int i = suffixArray[singletonPointer] + parentLcp;
			if (i>=string.length()) return false;
			if (string.charAt(i)=='$') return false;
			// does string begin with '$'? if so, text would be empty
			// --> return false
			if (string.charAt(suffixArray[singletonPointer])=='$')	return false;
			return true;
			
		}
		
		public boolean hasNext() {
			if (nextNodeIdx>=0) return true;
			if (singletonValid()) return true;
			return false;
		}
		
		public SuffixStructureNode next() {
			SuffixStructureNode result = null;
			if (nextNodeIdx>=0) {
				if (singletonPointer>nodeTable[nextNodeIdx].end) {
					result = new SingletonNode(singletonPointer, parentIdx);
					singletonPointer--;
				} else {
					result = new Node(nextNodeIdx);
					singletonPointer=nodeTable[nextNodeIdx].start-1;
					nextNodeIdx = getNextNodeIndex(nextNodeIdx);
				} 
			} else {
				if (singletonPointer>=parentIntervalStart) {
					if (singletonValid()){
						result = new SingletonNode(singletonPointer, parentIdx);
						singletonPointer--;
					}
				}
			}
			if (result!=null) return result;
			else throw new NoSuchElementException();
		}
		public void remove() { throw new UnsupportedOperationException(); }
	}
	
	private class Node extends AbstractSuffixStructureNode {
		int idx;
		Node(int idx) {
			this.idx=idx;
		}
		public Iterator<SuffixStructureNode> childrenIterator() {
			return new ChildrenIterator(idx);
		}
		public int getOneIndex() {
			return suffixArray[nodeTable[idx].start];
		}
		public String getText() {
			int start = suffixArray[nodeTable[idx].start];
			int end = start+nodeTable[idx].lcp;
			return string.substring(start, end);
		}
		public boolean isSuffix() {
			int i = suffixArray[nodeTable[idx].start];
			i+=nodeTable[idx].lcp;
			if (i>=string.length()) return true;
			if (string.charAt(i)=='$') return true;
			return false;
		}
		public boolean isRoot() { return idx==0; }
		public SuffixStructureNode getChildByChar(char c) {
			int lcp = nodeTable[idx].lcp;
			int last_child_idx = -1;
			int child_idx = -1;
			if (hasChild(idx)) child_idx = idx+1;
			while (child_idx>0) {
				char found_char = string.charAt(suffixArray[nodeTable[child_idx].start]+lcp); 
				if (c==found_char) {
					return new Node(child_idx);
				}
				// if first char of current node is smaller than sought char,
				// we can stop (because nodes are ordered anti-alphabetically)
				if (c>found_char) break;
				last_child_idx=child_idx;
				child_idx=nodeTable[child_idx].prevChild;
			}
			// check if there is a nonempty interval of leafs left to investigate
			int start;
			int end;
			if (child_idx>=0) start = nodeTable[child_idx].end+1;
			else start = nodeTable[idx].start;
			if (last_child_idx>=0) end = nodeTable[last_child_idx].start-1;
			else end = nodeTable[idx].end;
			for (int i=end; i>=start; --i) {
				int char_idx = suffixArray[i]+lcp;
				if (char_idx>=string.length()) continue;
				char found_char = string.charAt(char_idx);
				if (c==found_char) {
					return new SingletonNode(i, idx);
				}
				if (c>found_char) break;
				if (found_char=='$') break;
			}
			return null;
		}
		public SuffixStructureNode getParent() {
			if (nodeTable[idx].parent>=0) {
				return new Node(nodeTable[idx].parent);
			} else {
				return null;
			}
		}
		public String getEdgeText() {
			int start = suffixArray[nodeTable[idx].start];
			int end = start+nodeTable[idx].lcp;
			if (nodeTable[idx].parent>=0) {
				start+= nodeTable[nodeTable[idx].parent].lcp;
			} else {
				// if node has no parent, its the root
				return "";
			}
			return string.substring(start, end);
		}
		public int getNumber() {
			return idx;
		}
		@Override
		public boolean equals(Object obj) {
			if (!(obj instanceof Node)) return false;
			return idx==((Node)obj).idx;
		}
	}
	
	public EnhancedSuffixArray() {
		clear();
	}
	
	public void clear() {
		string = null;
		suffixArray = null;
		nodeTable = null;
	}

	/** Determines if tree node with given index has one or more children. */
	private boolean hasChild(int idx) {
		if (nodeTable[idx].prevChild>=0){
			if (nodeTable[idx].prevChild==idx+1) {
				return false;
			} else {
				return true;
			}
		} else {
			if (nodeTable[idx].prevChild==-2) {
				return true;
			} else {
				return false;
			}
		}
	}		
	
	public void build(String s) {
		string=s;
		suffixArray = SuffixArrayFactory.create(string);
		int [] lcpArray = LcpArrayFactory.create(string, suffixArray);
		
		// build node table
		LinkedList<NodeTableElement> intervals = new LinkedList<NodeTableElement>();
		Stack<NodeTableElement> stack = new Stack<NodeTableElement>();
		stack.push(new NodeTableElement(0,0,1));
		for (int i=0; i<lcpArray.length; i++) {
			int lb=i-1;
			while (lcpArray[i]<stack.peek().lcp) {
				NodeTableElement interval = stack.pop();
				interval.end=i-1;
				intervals.add(interval);
				lb=interval.start;
			}
			if (lcpArray[i]>stack.peek().lcp) {
				NodeTableElement interval = new NodeTableElement(lcpArray[i], lb, -1);
				stack.push(interval);
			}
		}
		while (!stack.isEmpty()) {
			NodeTableElement interval = stack.pop();
			interval.end=lcpArray.length-1;
			intervals.add(interval);
		}

		class HistoryEntry {
			int index;
			NodeTableElement node;
			HistoryEntry(NodeTableElement node, int index) {
				this.index=index;
				this.node=node;
			}
		}
		Stack<HistoryEntry> history = new Stack<HistoryEntry>();
		nodeTable = new NodeTableElement[intervals.size()];
		int k=0;
		while (!intervals.isEmpty()) {
			NodeTableElement node = intervals.removeLast();
			if (!history.isEmpty()) {
				if (history.peek().node.start>node.end) {
					// case: intervals do not overlap
					HistoryEntry last = history.pop();
					while (!history.isEmpty() && (history.peek().node.start>node.end)) {
						last = history.pop();
					}
					nodeTable[last.index].prevChild=k;
					node.parent=nodeTable[last.index].parent;
				} else {
					// case: child of node before
					nodeTable[k-1].prevChild=-2;
					node.parent=k-1;
				}
			}
			history.push(new HistoryEntry(node,k));
			nodeTable[k]=node;
			k+=1;
		}
	}

	public SuffixStructureNode getRoot() {
		if (nodeTable==null) return null;
		return new Node(0);
	}

}

